package elementaryAlgorithm;

import java.util.*;

import static java.util.Collections.reverse;

/**
 * 103. 二叉树的锯齿形层序遍历
 * 给定一个二叉树，返回其节点值的锯齿形层序遍历。（即先从左往右，再从右往左进行下一层遍历，以此类推，层与层之间交替进行）。
 *
 * 例如：
 * 给定二叉树 [3,9,20,null,null,15,7],
 *
 *     3
 *    / \
 *   9  20
 *     /  \
 *    15   7
 * 返回锯齿形层序遍历如下：
 *
 * [
 *   [3],
 *   [20,9],
 *   [15,7]
 * ]
 * */
public class ZigzagSequenceTraversalOfBinaryTree {

    public static void main(String[] args) {
        TreeNode node1 = new TreeNode(5);
        TreeNode node2 = new TreeNode(4);
        TreeNode node3 = new TreeNode(3,null,node1);
        TreeNode node4 = new TreeNode(2,node2,null);
        TreeNode root = new TreeNode(1,node4,node3);
        ZigzagSequenceTraversalOfBinaryTree sequenceTraversalOfBinaryTree = new ZigzagSequenceTraversalOfBinaryTree();
        List<List<Integer>> lists = sequenceTraversalOfBinaryTree.zigzagLevelOrder(root);
        System.out.println(lists);
    }


    public List<List<Integer>> zigzagLevelOrder(TreeNode root) {
        List<List<Integer>> result = new ArrayList<>();
        if (root == null){
            return result;
        }
        Queue<TreeNode> queue = new LinkedList<>();
        TreeNode node = root;
        queue.add(node);
        int length = 0;
        while (!queue.isEmpty()){
            length = queue.size();
            List<Integer> list = new ArrayList<>();
            while(length -- >0){
                node = queue.remove();
                list.add(node.val);
                if (node.left != null){
                    queue.add(node.left);
                }
                if (node.right != null){
                    queue.add(node.right);
                }
            }
            result.add(list);
        }
        for (int i = 0; i < result.size(); i++) {
            if (i % 2 == 1){
                reverse(result.get(i));
            }
        }
        return result;
    }
}
